{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Maze II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #array #matrix #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #数组 #矩阵 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #迷宫 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>迷宫</strong>中有一个球，它有空地 (表示为 <code>0</code>) 和墙 (表示为 <code>1</code>)。球可以<strong>向上</strong>、<strong>向下</strong>、<strong>向左</strong>或<strong>向右</strong>滚过空地，但直到撞上墙之前它都不会停止滚动。当球停止时，它才可以选择下一个滚动方向。</p>\n",
    "\n",
    "<p>给定 <code>m × n</code> 的<strong>迷宫</strong>(<code>maze</code>)，球的<strong>起始位置&nbsp;</strong>(<code>start = [start<sub>row</sub>, start<sub>col</sub>]</code>) 和<strong>目的地&nbsp;</strong>(<code>destination = [destination<sub>row</sub>, destination<sub>col</sub>]</code>)，返回球在<strong>目的地&nbsp;</strong>(<code>destination</code>) 停止的最短<strong>距离</strong>。如果球不能在<strong>目的地&nbsp;</strong>(<code>destination</code>) 停止，返回 <code>-1</code>。</p>\n",
    "\n",
    "<p><strong>距离</strong>是指球从起始位置 ( 不包括 ) 到终点 ( 包括 ) 所经过的<strong>空地</strong>数。</p>\n",
    "\n",
    "<p>你可以假设<strong>迷宫的边界都是墙&nbsp;</strong>( 见例子 )。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/31/maze1-1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解析:</strong> 一条最短路径 : left -&gt; down -&gt; left -&gt; down -&gt; right -&gt; down -&gt; right。\n",
    "             总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。\n",
    "\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/31/maze1-2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解析:</strong> 球不可能在目的地停下来。注意，你可以经过目的地，但不能在那里停下来。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]\n",
    "<strong>输出:</strong> -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == maze.length</code></li>\n",
    "\t<li><code>n == maze[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>maze[i][j]</code>&nbsp;是&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>.</li>\n",
    "\t<li><code>start.length == 2</code></li>\n",
    "\t<li><code>destination.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>row</sub>, destination<sub>row</sub>&nbsp;&lt; m</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>col</sub>, destination<sub>col</sub>&nbsp;&lt; n</code></li>\n",
    "\t<li>球和目的地都存在于一个空地中，它们最初不会处于相同的位置。</li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">迷宫<strong>至少包含两个空地</strong>。</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-maze-ii](https://leetcode.cn/problems/the-maze-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-maze-ii](https://leetcode.cn/problems/the-maze-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]\\n[0,4]\\n[4,4]', '[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]\\n[0,4]\\n[3,2]', '[[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]]\\n[4,3]\\n[0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        if start == destination:\n",
    "            return 0\n",
    "        \n",
    "        # queue = deque([tuple(start + [0])])\n",
    "        queue = [tuple([0] + start)]\n",
    "        \n",
    "\n",
    "        visited = {tuple(start) : 0}\n",
    "        # res = []\n",
    "\n",
    "        while queue:\n",
    "            # prev_x, prev_y, prev_distance = queue.popleft()\n",
    "            prev_distance, prev_x, prev_y = heappop(queue)\n",
    "            if [prev_x, prev_y] == destination:\n",
    "                return prev_distance\n",
    "            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                dist, x, y = prev_distance, prev_x, prev_y\n",
    "                while 0 <= x + dx < len(maze) and 0 <= y + dy < len(maze[0]) and maze[x + dx][y + dy] == 0:\n",
    "                    dist += 1\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "\n",
    "                if ((x, y) in visited and visited[(x, y)] > dist) or ((x, y) not in visited):\n",
    "                    visited[(x, y)] = dist\n",
    "                    heappush(queue, (dist, x, y))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "\n",
    "        directions = [(0,1),(1,0),(-1,0),(0,-1)]    # 定义上下左右四个方向\n",
    "        m = len(maze)                               # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "\n",
    "        queue = [(start[0],start[1])]               # 构造队列，并将起始位置包含其中\n",
    "                                                    # distance保存从起点到每个点的距离\n",
    "        distance = [[float('inf')]*n for _ in range(m)]\n",
    "        distance[start[0]][start[1]] = 0\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)                      # 弹出坐标值i,j\n",
    "                                                    # 如果坐标为终点坐标，返回True，程序结束\n",
    "            \n",
    "            for dx,dy in directions:                # 对四个方向进行遍历\n",
    "                x,y,step =i+dx,j+dy,distance[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y] != 1:                                      \n",
    "                                                    # 当x,y坐标合法，并且对应值为0或-1时\n",
    "                    x = x+dx                        # 继续前进，模拟小球的滚动过程\n",
    "                    y = y+dy                        # 其中0为空地，而-1为之前遍历过的空地\n",
    "                    step += 1\n",
    "\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "\n",
    "                if distance[x][y] > step:           # 如果起点到该点的距离比当前距离大\n",
    "                                                    # 更新该距离，并将坐标加入队列\n",
    "                    maze[x][y] = -1                 # 在maze中标记已经遍历过\n",
    "                    distance[x][y] = step              \n",
    "                    queue.append((x,y))             # 并将其坐标添加到队列中\n",
    "                                                    # 如果遍历所有可能性都无法达到目的地\n",
    "        return distance[destination[0]][destination[1]] if distance[destination[0]][destination[1]] != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "    \n",
    "        nrow = len(maze)\n",
    "        ncol = len(maze[0])\n",
    "        distance  = [[sys.maxsize for _ in range(ncol)] for _ in range(nrow) ]\n",
    "        distance[start[0]][start[1]] =0\n",
    "\n",
    "        directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        queue = deque([])\n",
    "        queue.append((start))\n",
    "\n",
    "\n",
    "        while queue:\n",
    "            i, j  = queue.popleft()\n",
    "\n",
    "            for x, y in directions:\n",
    "                row = i \n",
    "                col = j \n",
    "                temp_d = 0 \n",
    "                while 0 <= row+x < nrow and 0 <= col+y < ncol and maze[row+x][col+y] != 1:\n",
    "                    row += x   \n",
    "                    col += y \n",
    "                    temp_d += 1 \n",
    "\n",
    "                if distance[i][j] + temp_d < distance[row][col]:\n",
    "                    distance[row][col] = distance[i][j] + temp_d\n",
    "                    queue.append([row, col])\n",
    "\n",
    "        if distance[destination[0]][destination[1]] == sys.maxsize:\n",
    "            return -1 \n",
    "        return distance[destination[0]][destination[1]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "\n",
    "        DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        row = len(maze)\n",
    "        col = len(maze[0])\n",
    "\n",
    "        queue = [start]\n",
    "        distance = [[float('inf')] * col for i in range(row)]\n",
    "        distance[start[0]][start[1]] = 0\n",
    "\n",
    "        while queue:\n",
    "            r, c = queue.pop(0)\n",
    "            for x, y in DIRECTIONS:\n",
    "                _r, _c = x + r, y + c\n",
    "                steps = distance[r][c]\n",
    "\n",
    "                while 0 <= _r < row and 0 <= _c < col and maze[_r][_c] != 1:\n",
    "                    _r += x\n",
    "                    _c += y\n",
    "                    steps += 1\n",
    "                \n",
    "                _r -= x\n",
    "                _c -= y\n",
    "\n",
    "                if distance[_r][_c] > steps:\n",
    "                    distance[_r][_c] = steps\n",
    "                    #maze[_r][_c] = 2\n",
    "                    queue.append((_r, _c))\n",
    "        \n",
    "\n",
    "        return distance[destination[0]][destination[1]] if distance[destination[0]][destination[1]] != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "\n",
    "        n, m = len(maze), len(maze[0])\n",
    "\n",
    "        distances = [[math.inf] * m for _ in range(n)]\n",
    "        distances[start[0]][start[1]] = 0\n",
    "\n",
    "        q = collections.deque([start])\n",
    "\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            maze[x][y] = 2\n",
    "\n",
    "            for dx, dy in DIRECTIONS:\n",
    "                new_x, new_y = x, y\n",
    "                step = distances[x][y]\n",
    "                while self.is_valid(maze, new_x + dx, new_y + dy):\n",
    "                    new_x, new_y = new_x + dx, new_y + dy\n",
    "                    step += 1\n",
    "\n",
    "                if step < distances[new_x][new_y]:\n",
    "                    distances[new_x][new_y] = step\n",
    "                    q.append([new_x, new_y])\n",
    "\n",
    "        if distances[destination[0]][destination[1]] is not math.inf:\n",
    "            return distances[destination[0]][destination[1]]\n",
    "        return -1\n",
    "                \n",
    "    def is_valid(self, maze, x, y):\n",
    "        row, col = len(maze), len(maze[0])\n",
    "        return x >= 0 and x < row and y >= 0 and y < col and maze[x][y] != 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        marked = [[False for _ in range(n)] for _ in range(m)]\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        distance = [[float('inf')] * n for _ in range(m)]\n",
    "        distance[start[0]][start[1]] = 0\n",
    "        queue = [(start[0], start[1])]\n",
    "\n",
    "        while queue:\n",
    "            pop_i, pop_j = queue.pop(0)\n",
    "            for direction in directions:\n",
    "                new_i = pop_i + direction[0]\n",
    "                new_j = pop_j + direction[1]\n",
    "                step = distance[pop_i][pop_j]\n",
    "                while 0 <= new_i < m and 0 <= new_j < n and maze[new_i][new_j] != 1:\n",
    "                    new_i += direction[0]\n",
    "                    new_j += direction[1]\n",
    "                    step += 1\n",
    "                \n",
    "                new_i -= direction[0]\n",
    "                new_j -= direction[1]\n",
    "\n",
    "                if distance[new_i][new_j] > step:\n",
    "                    maze[new_i][new_j] = -1\n",
    "                    distance[new_i][new_j] = step\n",
    "                    queue.append((new_i, new_j))\n",
    "\n",
    "        return distance[destination[0]][destination[1]] if distance[destination[0]][destination[1]] != float('inf') else -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "\n",
    "        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]  # 定义上下左右四个方向\n",
    "        m = len(maze)  # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "\n",
    "        queue = [(start[0], start[1])]  # 构造队列，并将起始位置包含其中\n",
    "        # distance保存从起点到每个点的距离\n",
    "        distance = [[float('inf')] * n for _ in range(m)]\n",
    "        distance[start[0]][start[1]] = 0\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)  # 弹出坐标值i,j\n",
    "            # 如果坐标为终点坐标，返回True，程序结束\n",
    "\n",
    "            for dx, dy in directions:  # 对四个方向进行遍历\n",
    "                x, y, step = i + dx, j + dy, distance[i][j]\n",
    "                while 0 <= x < m and 0 <= y < n and maze[x][y] != 1:\n",
    "                    # 当x,y坐标合法，并且对应值为0或-1时\n",
    "                    x = x + dx  # 继续前进，模拟小球的滚动过程\n",
    "                    y = y + dy  # 其中0为空地，而-1为之前遍历过的空地\n",
    "                    step += 1\n",
    "\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "\n",
    "                if distance[x][y] > step:  # 如果起点到该点的距离比当前距离大\n",
    "                    # 更新该距离，并将坐标加入队列\n",
    "                    distance[x][y] = step\n",
    "                    queue.append((x, y))  # 并将其坐标添加到队列中\n",
    "                    # 如果遍历所有可能性都无法达到目的地\n",
    "        return distance[destination[0]][destination[1]] if distance[destination[0]][destination[1]] != float(\n",
    "            'inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze, start, destination): \n",
    "        m, n = len(maze), len(maze[0])\n",
    "        start, destination = tuple(start), tuple(destination)\n",
    "\n",
    "        queue = [(0, start)]\n",
    "        cloud = set([start])\n",
    "        while queue:\n",
    "            path, node = heappop(queue)\n",
    "            cloud.add(node)\n",
    "            if node == destination:\n",
    "                return path\n",
    "            i, j = node[0], node[1]\n",
    "            for x, y in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                ni, nj = i+x, j+y\n",
    "                count = 0\n",
    "                while 0<=ni<m and 0<=nj<n and maze[ni][nj]==0:\n",
    "                    ni, nj = ni+x, nj+y\n",
    "                    count += 1\n",
    "                ni, nj = ni-x, nj-y\n",
    "                if (ni, nj) not in cloud:\n",
    "                    heappush(queue, (path+count, (ni,nj)))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        row = len(maze)\n",
    "        col = len(maze[0])\n",
    "        visit = set()\n",
    "        def valid(x,y) -> bool:\n",
    "            if x < 0 or y < 0 or x >= row or y >= col or maze[x][y]:\n",
    "                return False\n",
    "            return True\n",
    "        dires = [[0,1],[0,-1],[-1,0],[1,0]]\n",
    "        arr = queue.PriorityQueue()\n",
    "        arr.put([0,start[0],start[1]])\n",
    "        res = []\n",
    "        while not arr.empty():\n",
    "            dis,x,y = arr.get_nowait()\n",
    "            if (x,y) in visit:\n",
    "                continue\n",
    "            visit.add((x,y))\n",
    "            for d in dires:\n",
    "                dd, xx,yy = dis,x,y\n",
    "                while valid(xx+d[0],yy+d[1]):\n",
    "                    xx += d[0]\n",
    "                    yy += d[1]\n",
    "                    dd += 1\n",
    "                if xx == destination[0] and yy == destination[1]:\n",
    "                    res.append(dd)\n",
    "                else:\n",
    "                    arr.put_nowait([dd, xx, yy])\n",
    "        if not res:\n",
    "            return -1\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        visited=set()\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        a,b=start\n",
    "        cur=[]\n",
    "        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "            if 0<=a+x<m and 0<=b+y<n and maze[a+x][b+y]==0:\n",
    "                visited.add((a+x,b+y,x+2*y))\n",
    "                cur.append((a+x,b+y,x,y))\n",
    "        step=1\n",
    "        while cur:\n",
    "            new_=[]\n",
    "            for a,b,x,y in cur:\n",
    "\n",
    "                if x!=0 and (a+x==m or a+x<0 or maze[a+x][b]==1):\n",
    "                    if [a,b]==destination:\n",
    "                        return step\n",
    "                    ##\n",
    "                    if b+1!=n and maze[a][b+1]==0 and (a,b+1,2) not in visited:\n",
    "                        visited.add((a,b+1,2))\n",
    "                        new_.append((a,b+1,0,1))\n",
    "                    if b-1>=0 and maze[a][b-1]==0 and (a,b-1,-2) not in visited:\n",
    "                        visited.add((a,b-1,-2))\n",
    "                        new_.append((a,b-1,0,-1))\n",
    "                    \n",
    "                elif y!=0 and (b+y==n or b+y<0 or maze[a][b+y]==1):\n",
    "                    if [a,b]==destination:\n",
    "                        return step\n",
    "                    ##\n",
    "                    if a+1!=m and maze[a+1][b]==0 and (a+1,b,1) not in visited:\n",
    "                        visited.add((a+1,b,1))\n",
    "                        new_.append((a+1,b,1,0))\n",
    "                    if a-1>=0 and maze[a-1][b]==0 and (a-1,b,-1) not in visited:\n",
    "                        visited.add((a-1,b,-1))\n",
    "                        new_.append((a-1,b,-1,0))\n",
    "                else:\n",
    "                    ##continue\n",
    "                    if  (a+x,b+y,x+2*y) not in visited:\n",
    "                        visited.add((a+x,b+y,x+2*y))\n",
    "                        new_.append((a+x,b+y,x,y))\n",
    "            step+=1\n",
    "            cur=new_\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        # 每个格子带了方向的属性，可以从不同方向滚动\n",
    "        # 0:up 1:down 2:left 3:right\n",
    "        # 一个方向需要走到头为止\n",
    "        n = len(maze)\n",
    "        m = len(maze[0])\n",
    "        dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        queue = deque()\n",
    "        queue.append((start[0], start[1], 0))\n",
    "        dis = [[inf] * m for i in range(n)]\n",
    "        dis[start[0]][start[1]] = 0\n",
    "        while len(queue):      \n",
    "            x, y, step = queue.popleft()\n",
    "            #if (x, y) == (destination[0], destination[1]):\n",
    "                #return step            \n",
    "            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:  # 左、右、上、下\n",
    "                if nx < 0 or ny < 0 or nx >= n or ny >= m or maze[nx][ny] == 1:\n",
    "                    continue\n",
    "                newStep = step\n",
    "                newStep += 1\n",
    "                if nx == x - 1: # 向左滚动\n",
    "                    while nx - 1 >= 0 and maze[nx-1][ny] == 0:\n",
    "                        nx = nx - 1\n",
    "                        newStep +=1                        \n",
    "                elif nx == x + 1:\n",
    "                    while nx + 1 < n and maze[nx+1][ny] == 0:\n",
    "                        nx = nx + 1\n",
    "                        newStep +=1                        \n",
    "                elif ny == y - 1:\n",
    "                    while ny - 1 >= 0 and maze[nx][ny-1] == 0:\n",
    "                        ny = ny - 1\n",
    "                        newStep +=1                        \n",
    "                else:\n",
    "                    while ny + 1 < m and maze[nx][ny+1] == 0:\n",
    "                        ny = ny + 1\n",
    "                        newStep +=1                        \n",
    "                if newStep < dis[nx][ny]:\n",
    "                    queue.append((nx, ny, newStep))\n",
    "                    dis[nx][ny] = newStep\n",
    "\n",
    "        if dis[destination[0]][destination[1]] != inf:\n",
    "            return dis[destination[0]][destination[1]]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        direction = [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        q = collections.deque([])\n",
    "        q.append([start[0],start[1]])\n",
    "        dis = [[float(\"inf\")] * n for _ in range(m)]\n",
    "        dis[start[0]][start[1]] = 0\n",
    "\n",
    "        while q:\n",
    "            i,j= q.popleft()\n",
    "            for d_x,d_y in direction:\n",
    "                x,y,step = i,j,dis[i][j]\n",
    "                while 0 <= x + d_x < m and 0 <= y + d_y < n and maze[x + d_x][y + d_y] != 1:\n",
    "                    x += d_x\n",
    "                    y += d_y\n",
    "                    step += 1\n",
    "                if dis[x][y] > step:\n",
    "                    maze[x][y] = -1\n",
    "                    dis[x][y] = step\n",
    "                    q.append([x,y])\n",
    "            # print(q)\n",
    "        return  dis[destination[0]][destination[1]] if dis[destination[0]][destination[1]] != float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        directions = [(0,1),(1,0),(-1,0),(0,-1)]    # 定义上下左右四个方向\n",
    "        m = len(maze)                               # 获取矩阵大小\n",
    "        n = len(maze[0])\n",
    "\n",
    "        queue = [(start[0],start[1])]               # 构造队列，并将起始位置包含其中\n",
    "                                                # distance保存从起点到每个点的距离\n",
    "        distance = [[float('inf')]*n for _ in range(m)]\n",
    "        distance[start[0]][start[1]] = 0\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)                      # 弹出坐标值i,j\n",
    "                                                # 如果坐标为终点坐标，返回True，程序结束\n",
    "        \n",
    "            for dx,dy in directions:                # 对四个方向进行遍历\n",
    "                x,y,step =i+dx,j+dy,distance[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y] != 1:                                      \n",
    "                                                # 当x,y坐标合法，并且对应值为0或-1时\n",
    "                    x = x+dx                        # 继续前进，模拟小球的滚动过程\n",
    "                    y = y+dy                        # 其中0为空地，而-1为之前遍历过的空地\n",
    "                    step += 1\n",
    "\n",
    "                x = x - dx\n",
    "                y = y - dy\n",
    "\n",
    "                if distance[x][y] > step:           # 如果起点到该点的距离比当前距离大\n",
    "                                                # 更新该距离，并将坐标加入队列\n",
    "                    maze[x][y] = -1                 # 在maze中标记已经遍历过\n",
    "                    distance[x][y] = step              \n",
    "                    queue.append((x,y))             # 并将其坐标添加到队列中\n",
    "                                                # 如果遍历所有可能性都无法达到目的地\n",
    "        return distance[destination[0]][destination[1]] if distance[destination[0]][destination[1]] != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        # dfs slow\n",
    "        # m, n = len(maze), len(maze[0])\n",
    "        # distance = [[ float(\"inf\") for a in range(n) ] for b in range(m)]\n",
    "        # distance [start[0]][start[1]] = 0\n",
    "        # directions = [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        # def dfs(x:int,y:int):\n",
    "        #     for i,j in directions:\n",
    "        #         k = 0\n",
    "        #         newX = x\n",
    "        #         newY = y\n",
    "        #         while 0 <= newX < m  and 0 <= newY < n and maze[newX][newY] == 0:\n",
    "        #             newX += i\n",
    "        #             newY += j\n",
    "        #             k += 1\n",
    "        #         if k > 0:\n",
    "        #             newX = newX - i\n",
    "        #             newY = newY - j\n",
    "        #             k -= 1\n",
    "                \n",
    "        #         if distance[x][y] + k < distance[newX][newY]:\n",
    "        #             distance[newX][newY] = distance[x][y] + k\n",
    "        #             dfs(newX,newY)\n",
    "\n",
    "        # dfs(start[0],start[1])\n",
    "        # return -1 if distance[destination[0]][destination[1]] == float(\"inf\") else distance[destination[0]][destination[1]]\n",
    "        # dijkstra \n",
    "        import heapq\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        queue = [(0,start)]\n",
    "        distance = [[ float(\"inf\") for a in range(n) ] for b in range(m)]\n",
    "        distance [start[0]][start[1]] = 0\n",
    "        heapq.heapify(queue)\n",
    "        # for row in distance:\n",
    "        #     print(row)\n",
    "        while queue:\n",
    "            dist,[x,y] = heapq.heappop(queue)\n",
    "            if distance[x][y] < dist :\n",
    "                continue\n",
    "            for i, j in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                k = 0\n",
    "                newX = x\n",
    "                newY = y\n",
    "                while 0 <= newX < m  and 0 <= newY < n and maze[newX][newY] == 0:\n",
    "                    newX += i\n",
    "                    newY += j\n",
    "                    k += 1\n",
    "                if k > 0:\n",
    "                    newX = newX - i\n",
    "                    newY = newY - j\n",
    "                    k -= 1\n",
    "                if distance[x][y] + k < distance[newX][newY]:\n",
    "                    distance[newX][newY] = distance[x][y] + k\n",
    "                    heapq.heappush(queue,(distance[newX][newY],[newX,newY]))\n",
    "        # for row in distance:\n",
    "        #     print(row)\n",
    "        return -1 if distance[destination[0]][destination[1]] == float(\"inf\") else distance[destination[0]][destination[1]]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        # dfs slow\n",
    "        # m, n = len(maze), len(maze[0])\n",
    "        # distance = [[ float(\"inf\") for a in range(n) ] for b in range(m)]\n",
    "        # distance [start[0]][start[1]] = 0\n",
    "        # directions = [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        # def dfs(x:int,y:int):\n",
    "        #     for i,j in directions:\n",
    "        #         k = 0\n",
    "        #         newX = x\n",
    "        #         newY = y\n",
    "        #         while 0 <= newX < m  and 0 <= newY < n and maze[newX][newY] == 0:\n",
    "        #             newX += i\n",
    "        #             newY += j\n",
    "        #             k += 1\n",
    "        #         if k > 0:\n",
    "        #             newX = newX - i\n",
    "        #             newY = newY - j\n",
    "        #             k -= 1\n",
    "                \n",
    "        #         if distance[x][y] + k < distance[newX][newY]:\n",
    "        #             distance[newX][newY] = distance[x][y] + k\n",
    "        #             dfs(newX,newY)\n",
    "\n",
    "        # dfs(start[0],start[1])\n",
    "        # return -1 if distance[destination[0]][destination[1]] == float(\"inf\") else distance[destination[0]][destination[1]]\n",
    "        # dijkstra \n",
    "\n",
    "        import heapq\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        queue = [(0,start[0],start[1])]\n",
    "        # distance = [[ float(\"inf\") for a in range(n) ] for b in range(m)]\n",
    "        # distance [start[0]][start[1]] = 0\n",
    "        # heapq.heapify(queue)\n",
    "        # for row in distance:\n",
    "        #     print(row)\n",
    "        d = {}\n",
    "        while queue:\n",
    "            dist,x,y = heapq.heappop(queue)\n",
    "            if (x,y) in d:\n",
    "                continue\n",
    "            if [x,y] == destination:\n",
    "                return dist\n",
    "            d[(x,y)] = dist\n",
    "            for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                newX, newY, k = x, y, dist\n",
    "                while 0 <= newX + i < m  and 0 <= newY +j < n and maze[newX+i][newY+j] == 0:\n",
    "                    newX, newY, k = newX + i, newY + j, k+1\n",
    "                if  (newX,newY) not in d:\n",
    "                    # heappush(queue, (k, [x,y]))\n",
    "                    heapq.heappush(queue, (k, newX,newY))\n",
    "        return -1\n",
    "        # while queue:\n",
    "        #     dist,[x,y] = heapq.heappop(queue)\n",
    "        #     if distance[x][y] < dist :\n",
    "        #         continue\n",
    "        #     for i, j in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "        #         k = 0\n",
    "        #         newX = x\n",
    "        #         newY = y\n",
    "        #         while 0 <= newX < m  and 0 <= newY < n and maze[newX][newY] == 0:\n",
    "        #             newX += i\n",
    "        #             newY += j\n",
    "        #             k += 1\n",
    "        #         if k > 0:\n",
    "        #             newX = newX - i\n",
    "        #             newY = newY - j\n",
    "        #             k -= 1\n",
    "        #         if distance[x][y] + k < distance[newX][newY]:\n",
    "        #             distance[newX][newY] = distance[x][y] + k\n",
    "        #             heapq.heappush(queue,(distance[newX][newY],[newX,newY]))\n",
    "        # # for row in distance:\n",
    "        # #     print(row)\n",
    "        # return -1 if distance[destination[0]][destination[1]] == float(\"inf\") else distance[destination[0]][destination[1]]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        N, M = len(maze), len(maze[0])\n",
    "        que = [start]\n",
    "        haspass = [[0]*M for _ in range(N)]\n",
    "        i, j = start[0], start[1]\n",
    "        haspass[i][j] = 1\n",
    "        mindist = [[M*N]*M for _ in range(N)]\n",
    "        mindist[i][j] = 0\n",
    "\n",
    "        while que:\n",
    "            print(f'que: {que}')\n",
    "            node = que[0]\n",
    "            que.pop(0)\n",
    "            i, j = node[0], node[1]\n",
    "            # # haspass[i][j] = 1\n",
    "            # if node == destination:\n",
    "            #     return True\n",
    "\n",
    "            for di, dj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                x, y = i+di, j+dj\n",
    "                while -1 < x < N and -1 < y < M and maze[x][y] == 0:\n",
    "                    x, y = x+di, y+dj\n",
    "                x, y = x-di, y-dj\n",
    "                print(f'(x,y) = ({x},{y})')\n",
    "                curdist = abs(x-i)+abs(y-j)+mindist[i][j]\n",
    "                if haspass[x][y] == 0 or curdist < mindist[x][y]:\n",
    "                    que.append([x, y])\n",
    "                    haspass[x][y] = 1\n",
    "                    mindist[x][y] = min(mindist[x][y], curdist)\n",
    "                    print(f'mindist[{x}][{y}] = {mindist[x][y]}')\n",
    "\n",
    "        \n",
    "        i, j = destination[0], destination[1]\n",
    "        if mindist[i][j] == M*N:\n",
    "            return -1\n",
    "        else:\n",
    "            return mindist[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        dist = [[float('inf')]*n for _ in range(m)]\n",
    "        dist[start[0]][start[1]] = 0 \n",
    "        queue = [(start[0], start[1])]\n",
    "\n",
    "        while len(queue)>0:\n",
    "            i, j = queue.pop(0)\n",
    "\n",
    "            for dx, dy in directions:\n",
    "                x, y, step = i+dx, j+dy, dist[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y]!=1:\n",
    "                    x, y = x+dx, y+dy   \n",
    "                    step += 1\n",
    "                x, y = x-dx, y-dy\n",
    "                if dist[x][y]>step:\n",
    "                   # maze[x][y] = -1\n",
    "                    dist[x][y] = step\n",
    "                    queue.append((x, y))\n",
    "        return dist[destination[0]][destination[1]] if dist[destination[0]][destination[1]]!=float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        directions=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        distances=[[float('inf')]*n for _ in range(m)]\n",
    "        distances[start[0]][start[1]]=0\n",
    "\n",
    "        queue=[(start[0],start[1])]\n",
    "        while queue:\n",
    "            i,j=queue.pop(0)\n",
    "            for dx,dy in directions:\n",
    "                x,y,step=i+dx,j+dy,distances[i][j]\n",
    "                while 0<=x<m and 0<=y<n and maze[x][y]!=1:\n",
    "                    x+=dx\n",
    "                    y+=dy\n",
    "                    step+=1\n",
    "                x-=dx\n",
    "                y-=dy\n",
    "                if distances[x][y]>step:\n",
    "                    distances[x][y]=step\n",
    "                    queue.append((x,y))\n",
    "        return distances[destination[0]][destination[1]] if distances[destination[0]][destination[1]]!=float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        q = deque()\n",
    "        q.append([start[0], start[1]])\n",
    "        dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        n, m = len(maze), len(maze[0])\n",
    "        d = [[inf for _ in range(m)] for _ in range(n)]\n",
    "        d[start[0]][start[1]] = 0\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            dist = d[x][y]\n",
    "            tmpx, tmpy, tmpdist = x, y, dist\n",
    "            for dx, dy in dxy:\n",
    "                a, b = x + dx, y + dy\n",
    "                while a >= 0 and a < n and b >= 0 and b < m and maze[a][b] == 0:\n",
    "                    x, y = x + dx, y + dy\n",
    "                    a, b = x + dx, y + dy\n",
    "                    dist += 1\n",
    "                # 只有距离变小才更新\n",
    "                if d[x][y] > dist:\n",
    "                    d[x][y] = dist\n",
    "                    q.append([x, y])\n",
    "                x, y, dist = tmpx, tmpy, tmpdist\n",
    "        return -1 if d[destination[0]][destination[1]] == inf else d[destination[0]][destination[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:   \n",
    "        row=len(maze)\n",
    "        col=len(maze[0])\n",
    "\n",
    "        #dijkstra\n",
    "        cost={}\n",
    "        # pre={}\n",
    "        cost[(start[0],start[1])]=0\n",
    "        hp=[(0,start[0],start[1])]\n",
    "        dir=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        while hp:\n",
    "            pcost,pr,pc=heapq.heappop(hp)\n",
    "            if cost[(pr,pc)]<pcost:\n",
    "                continue\n",
    "            if [pr,pc]==destination:\n",
    "                return pcost\n",
    "            \n",
    "            for offr,offc in dir:\n",
    "                nr=pr\n",
    "                nc=pc\n",
    "                ncost=-1\n",
    "                for c in range(1,max(col,row)+1):\n",
    "                    nc+=offc\n",
    "                    nr+=offr\n",
    "                    if 0<=nc<col and 0<=nr<row and maze[nr][nc]==1:\n",
    "                        if c>1:\n",
    "                            ncost=pcost+c-1                             \n",
    "                        break\n",
    "                    if nr==-1 or nc==-1 or nr==row or nc==col:\n",
    "                        if c>1:\n",
    "                            ncost=pcost+c-1\n",
    "                        break \n",
    "                if ncost!=-1:\n",
    "                    nc-=offc\n",
    "                    nr-=offr\n",
    "                    if (nr,nc) not in cost:\n",
    "                        cost[(nr,nc)]=ncost\n",
    "                        heapq.heappush(hp,(ncost,nr,nc))\n",
    "                    else:\n",
    "                        if cost[(nr,nc)]>ncost:\n",
    "                            cost[(nr,nc)]=ncost\n",
    "                            heapq.heappush(hp,(ncost,nr,nc))\n",
    "        # print(cost)       \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        heap = []\n",
    "        visited = set()\n",
    "        ds = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        for d in ds:\n",
    "            heapq.heappush(heap, (0, start[0], start[1], d))\n",
    "        while heap:\n",
    "            cost, i,j ,d = heapq.heappop(heap)\n",
    "            if (i, j, d) in visited:\n",
    "                continue\n",
    "            visited.add((i, j, d))\n",
    "            if [i, j] == destination:\n",
    "                return cost \n",
    "            for d in ds:\n",
    "                di = i \n",
    "                dj = j \n",
    "                while d[0] + di >= 0 and d[1] + dj >= 0 and d[0] + di < m and d[1] + dj < n and maze[d[0] + di][d[1] + dj] != 1:\n",
    "                    di += d[0]\n",
    "                    dj += d[1]\n",
    "                if (di, dj, d) not in visited:\n",
    "                    heapq.heappush(heap, (cost + abs(di - i) + abs(dj-j), di, dj, d))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        dq = collections.deque()\n",
    "        dirs = ((-1,0),(0,1),(1,0),(0,-1))\n",
    "        dq.append((start[0],start[1],0))\n",
    "        min_steps = {}\n",
    "        ans = [2**64]\n",
    "        can_reach = False\n",
    "\n",
    "        ctr = [0]\n",
    "\n",
    "        while len(dq)>0:\n",
    "            i, j, step = dq.popleft()\n",
    "            # print(i,j,step)\n",
    "            if i == destination[0] and j == destination[1]:\n",
    "                can_reach = True\n",
    "                ans[0] = min(ans[0], step)\n",
    "            min_steps[(i, j)] = step if (i, j) not in min_steps else min(min_steps[(i,j)], step)\n",
    "            for d in dirs:\n",
    "                ni, nj = i, j\n",
    "                add_step = 0\n",
    "                while 0<=ni+d[0]<len(maze) and 0<=nj+d[1]<len(maze[0]) and maze[ni+d[0]][nj+d[1]] != 1:\n",
    "                    ni+=d[0]\n",
    "                    nj+=d[1]\n",
    "                    add_step += 1\n",
    "                if (ni, nj) not in min_steps or min_steps[(ni,nj)] > step+add_step:\n",
    "                    dq.append((ni, nj, step+add_step))\n",
    "            \n",
    "        return ans[0] if can_reach else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        # 初始化信息\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        destination = tuple(destination)\n",
    "        start = tuple(start)\n",
    "        direc = {\"r\": [0, 1], \"l\": [0, -1], \"d\": [1, 0], \"u\": [-1, 0]}\n",
    "        \n",
    "        # 检查当前点是否到达合法\n",
    "        def check(node):\n",
    "            return 0<=node[0]<m and 0<=node[1]<n and not maze[node[0]][node[1]]\n",
    "        \n",
    "        # 最短距离采用广度优先搜索且起点合法的方向二元数组为位置pos与至今为止的方向\n",
    "        stack = [[start, d] for d in direc]\n",
    "\n",
    "        # 记忆化搜索按照轮次进行标记保证当前点当前方向不被更大的轮数搜索第二次\n",
    "        visit = defaultdict(dict)\n",
    "        cnt = 0\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for pos, d in stack:\n",
    "                visit[pos][d] = 1\n",
    "\n",
    "            # 找寻下一个经过的节点\n",
    "            for pos, d in stack:\n",
    "                node = (pos[0] + direc[d][0], pos[1] + direc[d][1])\n",
    "                # 停在目的地\n",
    "                if pos == destination and not check(node):\n",
    "                    return cnt\n",
    "                \n",
    "                # 下一个节点可达则继续前进\n",
    "                if check(node):\n",
    "                    if d not in visit[node]:\n",
    "                        nex.append([node, d])\n",
    "                # 否则就转换方向\n",
    "                else:\n",
    "                    for nd in direc:\n",
    "                        node = (pos[0] + direc[nd][0], pos[1] + direc[nd][1])\n",
    "                        if check(node) and nd not in visit[node]:\n",
    "                            nex.append([node, nd])\n",
    "            stack = nex[:]\n",
    "            cnt += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        INF = float(\"inf\")\n",
    "        n, m = len(maze), len(maze[0])\n",
    "\n",
    "        visited = [[INF for j in range(m)] for i in range(n)]\n",
    "\n",
    "        visited[start[0]][start[1]] = 0\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "\n",
    "        def dfs(x, y):\n",
    "\n",
    "            for i, j in directions:\n",
    "                nx, ny = x + i, y + j\n",
    "                count = 0\n",
    "                # 一直滚到墙壁\n",
    "                while 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 0:\n",
    "\n",
    "                    nx += i\n",
    "                    ny += j\n",
    "                    count += 1\n",
    "                #从当前位置滚到墙壁上的位置所需要的步数小于原先墙壁前位置的步数\n",
    "                if visited[x][y] + count < visited[nx - i][ny - j]:\n",
    "                    visited[nx - i][ny - j] = visited[x][y] + count\n",
    "                    dfs(nx - i, ny - j)\n",
    "        \n",
    "        dfs(start[0], start[1])\n",
    "\n",
    "        return visited[destination[0]][destination[1]] if visited[destination[0]][destination[1]] != INF else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        # f = [[[0] * 4 for _ in range(n)] for _ in range(m)]\n",
    "        dir = [0,-1,0,1,0] # left, up, right, down\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if maze[i][j] == 0:\n",
    "        #             for k in range(4):\n",
    "        #                 nx, ny = i + dir[k], j + dir[k + 1]\n",
    "        #                 if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "        #                 if f[nx][ny][k]:\n",
    "        #                     f[i][j][k] = f[nx][ny][k] + 1\n",
    "        #                     continue\n",
    "        #                 rx, ry = i - dir[k], j - dir[k + 1]\n",
    "        #                 if 0 <= rx < m and 0 <= ry < n and f[rx][ry][k]:\n",
    "        #                     f[i][j][k] = f[rx][ry][k] - 1\n",
    "        #                     continue\n",
    "        #                 d = 0\n",
    "        #                 while 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0:\n",
    "        #                     d += 1\n",
    "        #                     nx, ny = nx + dir[k], ny + dir[k + 1]\n",
    "        #                 f[i][j][k] = d                        \n",
    "        x, y = start\n",
    "        dx, dy = destination\n",
    "        pq = [(0, x, y, i) for i in range(4)]\n",
    "\n",
    "        vis = set()\n",
    "        while pq:\n",
    "            dist, x, y, k = heappop(pq)\n",
    "            if (x, y) == (dx, dy):\n",
    "                nx, ny = x + dir[k], y + dir[k + 1]\n",
    "                if not (0 <= nx < m and 0 <= ny < n) or maze[nx][ny]:\n",
    "                    return dist\n",
    "            if (x,y,k) in vis:\n",
    "                continue\n",
    "            vis.add((x,y,k))\n",
    "\n",
    "            nx, ny = x + dir[k], y + dir[k + 1]\n",
    "            d = 0\n",
    "            while 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0:\n",
    "                d += 1\n",
    "                nx, ny = nx + dir[k], ny + dir[k + 1]\n",
    "            if d:\n",
    "                heappush(pq,(dist + d, nx - dir[k], ny - dir[k + 1], k))\n",
    "            else:\n",
    "                for i in range(4):\n",
    "                    if i != k:\n",
    "                        heappush(pq, (dist, x, y, i))\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        # 统计从start发出的整个图，邻接表法\n",
    "        graph = {}\n",
    "        visited = set()\n",
    "        queue = deque()\n",
    "        queue.append(tuple(start))\n",
    "        while queue:\n",
    "            node = queue.pop()\n",
    "            graph[node] = []\n",
    "            visited.add(node)\n",
    "            i, j = node\n",
    "            l, r, u, d = j, j, i, i\n",
    "            while l > 0 and maze[i][l - 1] == 0: l -= 1\n",
    "            if l < j:\n",
    "                graph[tuple(node)].append((i, l))\n",
    "                if (i, l) not in visited:\n",
    "                    queue.append((i, l))\n",
    "            while r + 1 < n and maze[i][r + 1] == 0: r += 1\n",
    "            if r > j:\n",
    "                graph[tuple(node)].append((i, r))\n",
    "                if (i, r) not in visited:\n",
    "                    queue.append((i, r))\n",
    "            while u > 0 and maze[u - 1][j] == 0: u -= 1\n",
    "            if u < i:\n",
    "                graph[tuple(node)].append((u, j))\n",
    "                if (u, j) not in visited:\n",
    "                    queue.append((u, j))\n",
    "            while d + 1 < m and maze[d + 1][j] == 0: d += 1\n",
    "            if d > i:\n",
    "                graph[tuple(node)].append((d, j))\n",
    "                if (d, j) not in visited:\n",
    "                    queue.append((d, j))\n",
    "\n",
    "        def getMinDistanceAndUnSelectedNode(distanceDict, selectedNodes):\n",
    "            minNode = None\n",
    "            minDistance = float('inf')\n",
    "            for node, distance in distanceDict.items():\n",
    "                if distance < minDistance and node not in selectedNodes:\n",
    "                    minNode = node\n",
    "                    minDistance = distance\n",
    "            return minNode\n",
    "        # dijskra计算start节点到各节点的距离\n",
    "        distanceDict = {}\n",
    "        selectedNodes = set()\n",
    "        distanceDict[tuple(start)] = 0\n",
    "        minNode = getMinDistanceAndUnSelectedNode(distanceDict, selectedNodes)\n",
    "        while minNode:\n",
    "            dis = distanceDict[minNode]\n",
    "            for node in graph[minNode]:\n",
    "                if node not in distanceDict:\n",
    "                    distanceDict[node] = dis + abs(minNode[0] + minNode[1] - node[0] - node[1])\n",
    "                else:\n",
    "                    distanceDict[node] = min(distanceDict[node], dis + abs(minNode[0] + minNode[1] - node[0] - node[1]))\n",
    "            selectedNodes.add(minNode)\n",
    "            minNode = getMinDistanceAndUnSelectedNode(distanceDict, selectedNodes)\n",
    "        if tuple(destination) in distanceDict:\n",
    "            return distanceDict[tuple(destination)]\n",
    "        return -1\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
